package org.matheclipse.combinatoric;

import java.util.Iterator;

/**
 * <p>
 * Combinations of a multiset
 * </p>
 * <p>
 * These are the combinations of <code>k</code> elements chosen from a sorted
 * <code>int[]</code> array, that can contain duplicates (a multiset).
 * </p>
 * <p>
 * For example, given the multiset <code>{0, 1, 1, 2, 2, 2, 3}</code>, the
 * 4-combinations are:
 * </p>
 * 
 * <pre>
 * [0, 1, 1, 2]
 * [0, 1, 1, 3]
 * [0, 1, 2, 2]
 * [0, 1, 2, 3]
 * [0, 2, 2, 2]
 * [0, 2, 2, 3]
 * [1, 1, 2, 2]
 * [1, 1, 2, 3]
 * [1, 2, 2, 2]
 * [1, 2, 2, 3]
 * [2, 2, 2, 3]
 * </pre>
 * 
 * <p>
 * This algorithm produces the combinations in lexicographic order, with the
 * elements in each combination in increasing order.
 * </p>
 * <p>
 * Begin with the first combination, which is the first <var>k</var> elements of
 * the multiset ([0, 1, 1, 2] in the example above), and then at each step:
 * </p>
 * <ol>
 * <li>Find the rightmost element that is less than the maximum value it can
 * have (which is the element in the multiset that is the same distance from the
 * right).
 * <li>Replace it with the first multiset element greater than it.
 * <li>Replace the remainder of the combination with the elements that follow
 * the replacement in the multiset.
 * </ol>
 * 
 * <p>
 * See: <a href="http://www.martinbroadhurst.com/combinatorial-algorithms.html#combinations-of-a-multiset"
 * >martinbroadhurst.com Combinations of a Multiset</a>
 */
public class MultisetCombinationIterator implements Iterator<int[]> {

	private int[] result;
	private final int[] multiset;
	private final int n;
	private final int k;

	/**
	 * <p>
	 * Combinations of a multiset
	 * </p>
	 * <p>
	 * These are the combinations of <code>k</code> elements chosen from a sorted
	 * <code>int[]</code> array, that can contain duplicates (a multiset).
	 * </p>
	 */
	public MultisetCombinationIterator(int[] multiset, final int k) {
		this.multiset = multiset;
		this.n = multiset.length;
		this.k = k;
		this.result = null;
	}

	public void reset() {
		this.result = null;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @see Iterator#next()
	 */
	public int[] next() {
		if (result == null) {
			result = new int[k];
			System.arraycopy(multiset, 0, result, 0, k);
		} else { 
			for (int i = k - 1; i >= 0; i--) {
				if (result[i] < multiset[i + (n - k)]) {
					// Find the successor
					int j;
					for (j = 0; multiset[j] <= result[i]; j++) {

					}
					// Replace this element with it
					result[i] = multiset[j];
					if (i < k - 1) {
						// Make the elements after it the same as this part of the multiset
						int l;
						for (l = i + 1, j = j + 1; l < k; l++, j++) {
							result[l] = multiset[j];
						}
					}
					return result;
				} 
			}
		}
		return result;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @see Iterator#hasNext()
	 */
	public final boolean hasNext() {
		if (result == null) {
			return true;
		}
		for (int i = k - 1; i >= 0; i--) {
			if (result[i] < multiset[i + (n - k)]) {
				return true;
			} 
		}
		return false;
	}

	/**
	 * Throws an UnsupportedOperationException
	 */
	@Override
	public void remove() {
		throw new UnsupportedOperationException("This iterator doesn't support the remove() method");
	}

}
